package offer;

@FunctionalInterface
public interface IsToeplitzMatrix {
    /**
     * Given an m x n matrix, return true if the matrix is Toeplitz. Otherwise, return false.
     *
     * A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements.
     *
     * @param matrix
     * @return
     */
    boolean isToeplitzMatrix(int[][] matrix);
}
class IsToeplitzMatrixImpl1 implements IsToeplitzMatrix{
    static final int[][] TEST_01 = new int[][]{{1, 2, 3, 4}, {5, 1, 2, 3}, {9, 5, 1, 2}};
    static final int[][] TEST_02 = new int[][]{{36, 59, 71, 15, 26, 82, 87}, {56, 36, 59, 71, 15, 26, 82}, {15, 0, 36, 59, 71, 15, 26}};
    public static void main(String[] args) {
        new IsToeplitzMatrixImpl1().isToeplitzMatrix(TEST_02);
    }
    private int m;
    private int n;

    /**
     * 暴力检查所有对角线
     * @param matrix
     * @return
     */
    @Override
    public boolean isToeplitzMatrix(int[][] matrix) {
        boolean ans = true;
        m = matrix.length;
        n = matrix[0].length;
        int iter = 0;
        // 处理主对角线以上的元素
        while(iter < n - 1 && ans){
            ans = processDiagonal(0, iter, matrix);
            iter++;
        }
        // 处理主对角线以下的元素
        iter = 1;
        while(iter < m - 1 && ans){
            ans = processDiagonal(iter, 0, matrix);
            iter++;
        }
        return ans;
    }

    /**
     * 判断点 x，y所在对角线是否符合题意
     * @param x
     * @param y
     * @param matrix
     * @return
     */
    private boolean processDiagonal(int x,int y,int[][] matrix){
        int curElement = matrix[x][y];
        int i = x, j = y;
        while(isValidPoint(i,j)){
            if(curElement != matrix[i][j]){
                return false;
            }
            i++;
            j++;
        }
        return true;
    }
    public boolean isValidPoint(int x, int y){
        if(x >= 0 && y >=0 && x < m && y < n){
            return true;
        }else{
            return false;
        }
    }
}
